1. Field of the Invention
The present invention relates to a method and apparatus for encoding and decoding an image.
2. Description of the Related Art
A description will be given of a conventional encoding and decoding scheme, more specifically, a generally known technique of lossless coding of a multi-level image.
As a conventional technique of lossless coding of a multi-level image, an international standard of "Independent Function" set forth in ITU-T recommendation T.81 (JPEG) is known. This is a differential pulse code modulation (DPCM) coding scheme for entropy coding a prediction error signal of a pixel subject to encoding, in which the entropy coding scheme may be selected between Huffman encoding or arithmetic encoding (QM-Coder). Here, a description will be given of a scheme using arithmetic encoding which has high encoding efficiency. Block diagrams of its encoding/decoding processes are shown in FIGS. 48 and 49.
First, a description will be given of an encoding process. In FIG. 48, an image line memory 101 stores a multi-level image to be encoded, and outputs that encoding pixel and one or a plurality of stored pixels in the vicinity of that encoding pixel as a reference pixel. A predictor 102 predicts the encoding pixel in a line including the encoding pixel (X) stored in the image line memory 101 and in a line preceding the same. As shown in FIG. 50, prediction is effected by referring to pixels in the vicinity of the encoding pixel X. At this time, as a function for prediction, only one function is selected from among seven kinds of functions (fixed predictive functions) at the time of encoding one screen, as shown in FIG. 50. Then, a prediction error V between the encoding pixel X and a prediction value P obtained from the predictor 102 is determined by X-P, and is transformed into a binary symbol (0/1) string by a binarizing transformer 103. In the binarizing transformer 103, the prediction error V is transformed into the binary symbol (0/1) string in the procedure shown below, and code words are assigned by binary arithmetic encoding in an arithmetic encoder 104.
(1) Determination and encoding of V=0 PA0 (2) Determination and encoding of the positive/negative sign of V PA0 (3) Encoding of group number PA0 (1) Decoding of S.sub.0 and determination of V=0 PA0 (2) Decoding of S.sub.1 and determination of the positive/negative sign of V PA0 (3) Decoding and transformation into group number PA0 (4) Decoding and transformation into Sz (applied to group number 2 and subsequent group numbers)
If V=0, 0 is encoded, and the encoding of the present pixel ends, whereupon the operation proceeds to an ensuing pixel.
If V.noteq.0, 1 is encoded, and the operation proceeds to the processing step (2) and subsequent steps.
If V&gt;0, 0 is encoded, and if V&lt;0, 1 is encoded.
The number of a group (see FIG. 51) to which Sz=.vertline.v.vertline.-1 belongs is binarized and encoded. Namely, in an ascending order starting from the group number 0, 1 is encoded if Sz does not belong to a group, and 0 is encoded if it does. For instance, in the case of group number 3, 1110 is encoded. p0 (4) Encoding of additional bits (applied to group number 2 and subsequent group numbers)
Additional bits indicating which value Sz represents in the group are encoded. That is, bits corresponding to the number of additional bits (see FIG. 51) starting from the lowest-order bit when Sz is expressed in natural binary notation are encoded sequentially starting from the highest-order bit thereof (the encoding is not required for group numbers 0 and 1).
When the encoding of the binary symbol (0/1) string is carried out in the arithmetic encoder 104, it is necessary to predict the probability of generating 0 or 1 in each symbol and effect encoding which is most appropriate for that symbol. For this reason, the context of each symbol is generated by a context generator 105 on the basis of the state of a pixel neighboring the encoding pixel X as well as the conditions under which the binary symbol string was generated by the binarizing transformer 103. By inputting the contexts and the symbols to the arithmetic encoder 104, probability parameters representing the prediction probability are stored for each context, so as to effect the encoding efficiently.
FIG. 52 shows a method of generating the context by the context generator 105 by making use of each determining condition obtained by the binarizing transformer 103. Further, at this time, the prediction error (V) of a prediction value from the encoding pixel X is stored in advance in a prediction error memory 106, and the context is discriminated on the basis of the relative magnitude of the error which is determined from FIG. 53. Thus, as for the encoding process, the encoding of one screen is effected by repeating the above-described processing until there ceases to be a pixel to be encoded.
Next, a description will be given of the decoding operation with reference to FIG. 49. During decoding, operation which is opposite to the encoding operation is basically carried out. The encoded data to be decoded is inputted to an arithmetic decoder 108, and is decoded into a binary symbol (0/1) string (it is assumed that the present pixel is decoded starting with S.sub.0, and its i-th symbol is set as S.sub.i). Next, this binary symbol string is inputted to a multi-level transformer 107, and is transformed into the prediction error (V) in the following procedure.
If S.sub.0 =0, it is assumed that the prediction error V=0, and the decoding of the present pixel is finished.
If S.sub.0 =1, the operation proceeds to the processing step (2) and subsequent steps.
If S.sub.1 =0, it is judged that V&gt;0. If S.sub.1 =1, then it is judged that V&lt;0.
The number of the group (see FIG. 51) to which Sz=.vertline.v.vertline.-1 belongs is determined from the binary symbol of S.sub.2 and subsequent symbols. Namely, decoding is repeated until the symbol 0 is detected, and the number of symbols 1 continuing from S.sub.2 is the group number (assumed to be GN). For instance, if the binary symbol string for determination of the group number is 1110, the group number is 3.
A determination is made as to which value Sz represents in the group, on the basis of the fact that a binary symbol string corresponding to the number of additional bits (see FIG. 51) of S.sub.3+ GN and subsequent symbols corresponds to the number of additional bits starting from the lowest-order bit when Sz is expressed in natural binary notation (the determination is not required for the group numbers 0 and 1).
At this time, the prediction error (V) obtained by the multi-level transformer 107 is stored in the prediction error memory as an error value in the vicinity of the pixel to be decoded in the same way as in the encoding process, and the context generator 105 generates a context required for the arithmetic decoder 108 at the time of decoding. Then, as for the prediction error (V) obtained by the multi-level transformer 107, since the value of the neighboring pixel already decoded as a pixel value prior to the pixel subject to decoding is stored in an image line memory 101d, the value of the pixel subject to decoding can be determined from X=P+V for the prediction value P obtained by the predictor 102 in the same way as in the decoding process. Thus, as for the decoding operation, the decoding of one screen is effected by repeating the above-described processing until there ceases to be a pixel to be decoded.
With the above-described conventional image encoding apparatus and decoding apparatus, since an image is predicted by using a fixed predictive function in one scan, the method is not necessarily suitable to a state of distribution of pixels in a local image area, so that there has been a problem in that the encoding and decoding efficiency declines. In addition, in the case of the prediction error which is entropy coded or decoded, disassembly or assembly must be carried out on the basis of the zero determination of the prediction error, the determination of the positive and negative, the determination of a group, and the meaning of additional bits, and a binary signal of a fixed length must be encoded or decoded for each determined group. Hence, here has been a problem in that the processing efficiency in encoding and decoding declines.